1. Field of the Invention
This invention relates to digital image processing.
2. Description of the Prior Art
Some digital image processing apparatus provides the ability for the user to create an arbitrary closed curve, for example a type of curve known as a spline, on a display screen. Image processing is then carried out depending on whether each point on the image lies inside or outside the closed curve.
A very simple example is that of a graphics drawing system, where a closed spline curve can be created and then xe2x80x9cfilledxe2x80x9d with a wash of a particular display colour. Other more complicated examples occur in the field of video special effects processing, where closed curves of this nature can be used to define regions of an image where a particular special effect is to be performed.
There is therefore a need to establish which points in an image lie inside such a closed curve, and which lie outside. (Points lying on the curve are much easier to detect, and can be defined by convention as lying inside or outside the curve).
Various techniques have been proposed to perform this test, but many tend to fail with complicated curves such as those schematically illustrated in FIGS. 1a and 1b of the accompanying drawings.
This invention provides a method of digital image processing for detecting whether a test point within a digital representation of an image lies inside or outside a closed curve defined by an ordered series of curve points within the representation of the image, the method comprising the steps of:
(i) detecting an angle subtended at the test point by pairs of the curve points adjacent to one another in the ordered series;
(ii) summing the detected angles for all pairs of the curve points adjacent to one another in the ordered series; and
(iii) detecting whether the summed angle is equal to a non-zero integral multiple of 360xc2x0, thereby indicating that the test point lies within the closed curve.
The invention provides a method of assessing whether a test point lies inside or outside a closed curve by simply adding up the angles subtended at the test point by all possible adjacent pairs of points defining the curve. If this sum equals zero, then the test point is outside the curve. If the sum equals n.360xc2x0, where n is a non-zero integer, then the test point is within the curve. The method has been shown to be more reliable than previous techniques, particularly when dealing with xe2x80x9cdifficultxe2x80x9d curves such as those shown in FIGS. 1a and 1b. 
The skilled man will of course realise that the use of the unit xe2x80x9cdegreexe2x80x9d in a definition of the invention and embodiments below is not material to their operation. In fact, whatever units are used in the technique, the important test is whether the summed angle equals a non-zero integral multiple of the angle subtended by a closed circle.
Test points actually lying on the closed curve can be defined by convention to be inside or outside the curve. If such points are defined as being outside the curve then they are correctly detected by the test described above. In another preferred embodiment such points are defined as being inside the curve, and so the method also comprises the step of detecting whether the test point lies on the closed curve. This test could be performed before or after the xe2x80x9cmainxe2x80x9d test to detect whether the test point lies inside or outside the curve.
Preferably the representation of the image comprises an array of pixel values.
The value xe2x80x9cnxe2x80x9d mentioned above can also be very useful in itself, because as well as indicating whether the test point lies inside or outside the curve it can also give an indication of how many times the curve winds around that test point. So, if xe2x80x9cnxe2x80x9d is 3, then the curve makes three loops around the test point. If the detected value of xe2x80x9cnxe2x80x9d is xe2x88x923, then the curve still makes three loops around the test point but in an opposite sense.
The invention also provides digital image processing apparatus for detecting whether a test point within a digital representation of an image lies inside or outside a closed curve defined by an ordered series of curve points within the representation of the image, the apparatus comprising:
(i) means for detecting an angle subtended at the test point by pairs of the curve points adjacent to one another in the ordered series;
(ii) means for summing the detected angles for all pairs of the curve points adjacent to one another in the ordered series; and
(iii) means for detecting whether the summed angle is equal to a non-zero integral multiple of 360xc2x0, thereby indicating that the test point lies within the closed curve.
The above, and other objects, features and advantages of this invention will be apparent from the following detailed description of illustrative embodiments which is to be read in connection with the accompanying drawings.